P and NP
Sets for decision problems.
Definition
- P: Set of problems that are can be solved in polynomial time, called "tractable".
- NP: Superset of P, with problems whose solutions can be verified in polynomial time.
- NP-Hard: At least as hard as the hardest problem in NP.
- NP-Complete: In NP and as hard as the hardest problem in NP.
Reduction
Problem A can be transformed to problem B in polynomial time. So A's solver is in polynomial time if B's solver is also in polynomial time.
Since the solver chain is one-directional, we then know that A is no harder than B, or, B is at least as hard as A.
- If B is NP-hard, then A is no harder than NP-hard.
- If A is NP-hard, then B is at least NP-hard.
Why NP-completeness is SO important?
All NP-complete problems can be transformed into each other.
If there is a polynomial time solver for one NP-complete problem, then it can be used for all other problems.
This problem is known as: P = NP? (Does there exist a polynomial time solver for a NP-complete problem?)
Optimization Problem
A special type of decision problem.
If Your Problem is NP-hard
- Look for good approximation algorithm with provable grantees.
- Look for tractable subclasses.
- Use heuristics - try to do well on "most" cases.